#include <linux/hrtimer.h>

/*
 * The write_seqcount_barrier()s in __run_hrtimer() split the thing into 3
 * distinct sections:
 *
 *  - queued:	the timer is queued
 *  - callback:	the timer is being ran
 *  - post:	the timer is inactive or (re)queued
 *
 * On the read side we ensure we observe timer->state and cpu_base->running
 * from the same section, if anything changed while we looked at it, we retry.
 * This includes timer->base changing because sequence numbers alone are
 * insufficient for that.
 *
 * The sequence numbers are required because otherwise we could still observe
 * a false negative if the read side got smeared over multiple consecutive
 * __run_hrtimer() invocations.
 */

static void __run_hrtimer(struct hrtimer_cpu_base *cpu_base,
                          struct hrtimer_clock_base *base,
                          struct hrtimer *timer, ktime_t *now,
                          unsigned long flags)
{
    enum hrtimer_restart (*fn)(struct hrtimer *);
    bool expires_in_hardirq;
    int restart;

    lockdep_assert_held(&cpu_base->lock);

    debug_deactivate(timer);
    base->running = timer;

    /*
     * Separate the ->running assignment from the ->state assignment.
     *
     * As with a regular write barrier, this ensures the read side in
     * hrtimer_active() cannot observe base->running == NULL &&
     * timer->state == INACTIVE.
     */
    raw_write_seqcount_barrier(&base->seq);

    __remove_hrtimer(timer, base, HRTIMER_STATE_INACTIVE, 0);
    fn = ACCESS_PRIVATE(timer, function);

    /*
     * Clear the 'is relative' flag for the TIME_LOW_RES case. If the
     * timer is restarted with a period then it becomes an absolute
     * timer. If its not restarted it does not matter.
     */
    if (IS_ENABLED(CONFIG_TIME_LOW_RES))
        timer->is_rel = false;

    /*
     * The timer is marked as running in the CPU base, so it is
     * protected against migration to a different CPU even if the lock
     * is dropped.
     */
    raw_spin_unlock_irqrestore(&cpu_base->lock, flags);
    trace_hrtimer_expire_entry(timer, now);
    expires_in_hardirq = lockdep_hrtimer_enter(timer);

    restart = fn(timer);

    lockdep_hrtimer_exit(expires_in_hardirq);
    trace_hrtimer_expire_exit(timer);
    raw_spin_lock_irq(&cpu_base->lock);

    /*
     * Note: We clear the running state after enqueue_hrtimer and
     * we do not reprogram the event hardware. Happens either in
     * hrtimer_start_range_ns() or in hrtimer_interrupt()
     *
     * Note: Because we dropped the cpu_base->lock above,
     * hrtimer_start_range_ns() can have popped in and enqueued the timer
     * for us already.
     */
    if (restart != HRTIMER_NORESTART &&
        !(timer->state & HRTIMER_STATE_ENQUEUED))
        enqueue_hrtimer(timer, base, HRTIMER_MODE_ABS);

    /*
     * Separate the ->running assignment from the ->state assignment.
     *
     * As with a regular write barrier, this ensures the read side in
     * hrtimer_active() cannot observe base->running.timer == NULL &&
     * timer->state == INACTIVE.
     */
    raw_write_seqcount_barrier(&base->seq);

    WARN_ON_ONCE(base->running != timer);
    base->running = NULL;
}

static void __hrtimer_run_queues(struct hrtimer_cpu_base *cpu_base, ktime_t now,
                                 unsigned long flags, unsigned int active_mask)
{
    struct hrtimer_clock_base *base;
    unsigned int active = cpu_base->active_bases & active_mask;

    for_each_active_base(base, cpu_base, active)
    {
        struct timerqueue_node *node;
        ktime_t basenow;

        basenow = ktime_add(now, base->offset);

        while ((node = timerqueue_getnext(&base->active)))
        {
            struct hrtimer *timer;

            timer = container_of(node, struct hrtimer, node);

            /*
             * The immediate goal for using the softexpires is
             * minimizing wakeups, not running timers at the
             * earliest interrupt after their soft expiration.
             * This allows us to avoid using a Priority Search
             * Tree, which can answer a stabbing query for
             * overlapping intervals and instead use the simple
             * BST we already have.
             * We don't add extra wakeups by delaying timers that
             * are right-of a not yet expired timer, because that
             * timer will have to trigger a wakeup anyway.
             */
            if (basenow < hrtimer_get_softexpires_tv64(timer))
                break;

            __run_hrtimer(cpu_base, base, timer, &basenow, flags);
            if (active_mask == HRTIMER_ACTIVE_SOFT)
                hrtimer_sync_wait_running(cpu_base, flags);
        }
    }
}
